﻿#pragma once
#include "stdafx.h"

/*
三数之和  中等
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 

 示例：

 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

 满足要求的三元组集合为：
 [
 [-1, 0, 1],
 [-1, -1, 2]
 ]

 解题思路，在第一题目的时候，采用了hashmap的方式来解决两个数相加，此题变成了3个，方法差不多，
 可以先对序列排序，然后利用目标，来判断。然后去除重复的数组。时间复杂度为O(n^2)

*/

vector<vector<int> > threeSum(vector<int>& nums) 
{
	vector<vector<int>> result;
	sort(nums.begin(), nums.end());
	// 找出a + b + c = 0 
	// a = nums[i], b = nums[j], c = -(a + b)
	for (int i = 0; i < nums.size(); i++) {
		// 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
		if (nums[i] > 0) {
			continue;
		}
		if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
			continue;
		}
		unordered_set<int> set;
		for (int j = i + 1; j < nums.size(); j++) {
			if (j > i + 2
				&& nums[j] == nums[j - 1]
				&& nums[j - 1] == nums[j - 2]) { // 三元组元素b去重
				continue;
			}
			int c = 0 - (nums[i] + nums[j]);
			if (set.find(c) != set.end()) 
			{
				result.push_back({ nums[i], nums[j], c });
				set.erase(c);// 三元组元素c去重
			}
			else 
			{
				set.insert(nums[j]);
			}
		}
	}
	return result;
}



